// 环形链表
package Leetcode;

import java.util.ArrayList;
import java.util.List;

// 列表，空间复杂度O(n)
class Solution_141_1 {
    public boolean hasCycle(ListNode head) {
        List<ListNode> map = new ArrayList<>();
        while (head != null) {
            if (map.contains(head))
                return true;
            map.add(head);
            head = head.next;
        }
        return false;
    }
}

// Floyd判圈算法
class Solution_141_2 {
    public boolean hasCycle(ListNode head) {
        if (head == null)
            return false;
        ListNode slow = head;
        ListNode fast = head;
        do {
            if (slow.next == null || fast.next == null || fast.next.next == null)
                return false;
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);
        return true;
    }
}